DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2012.534

The Complexity of Quantitative Information Flow in Recursive Programs

Authors: Rohit Chadha and Michael Ummels

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract

Information-theoretic measures based upon mutual information can be employed to quantify the information that an execution of a program reveals about its secret inputs. The information leakage bounding problem asks whether the information leaked by a program does not exceed a given threshold. We consider this problem for two scenarios: a) the outputs of the program are revealed, and b)the timing (measured in the number of execution steps) of the program is revealed. For both scenarios, we establish complexity results in the context of deterministic boolean programs, both for programs with and without recursion. In particular, we prove that for recursive programs the information leakage bounding problem is no harder than checking reachability.

Cite as

Rohit Chadha and Michael Ummels. The Complexity of Quantitative Information Flow in Recursive Programs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 534-545, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{chadha_et_al:LIPIcs.FSTTCS.2012.534,
  author =	{Chadha, Rohit and Ummels, Michael},
  title =	{{The Complexity of Quantitative Information Flow in Recursive Programs}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{534--545},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.534},
  URN =		{urn:nbn:de:0030-drops-38872},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.534},
  annote =	{Keywords: quantitative information flow, recursive programs, program analysis, verification, computational complexity}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2011.375

Nash Equilibria in Concurrent Games with Büchi Objectives

Authors: Patricia Bouyer, Romain Brenguier, Nicolas Markey, and Michael Ummels

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract

We study the problem of computing pure-strategy Nash equilibria in multiplayer concurrent games with Büchi-definable objectives. First, when the objectives are Büchi conditions on the game, we prove that the existence problem can be solved in polynomial time. In a second part, we extend our technique to objectives defined by deterministic Büchi automata, and prove that the problem then becomes EXPTIME-complete. We prove PSPACE-completeness for the case where the Büchi automata are 1-weak.

Cite as

Patricia Bouyer, Romain Brenguier, Nicolas Markey, and Michael Ummels. Nash Equilibria in Concurrent Games with Büchi Objectives. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 375-386, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{bouyer_et_al:LIPIcs.FSTTCS.2011.375,
  author =	{Bouyer, Patricia and Brenguier, Romain and Markey, Nicolas and Ummels, Michael},
  title =	{{Nash Equilibria in Concurrent Games with B\"{u}chi Objectives}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{375--386},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.375},
  URN =		{urn:nbn:de:0030-drops-33340},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.375},
  annote =	{Keywords: Concurrent games, Nash equilibria, B\"{u}chi Objectives}
}

Search Results

Documents authored by Ummels, Michael

The Complexity of Quantitative Information Flow in Recursive Programs

Abstract

Cite as

Nash Equilibria in Concurrent Games with Büchi Objectives

Abstract

Cite as

Thanks for your feedback!

Could not send message